#ifndef LISTS_C
#define LISTS_C

#include <stdio.h> 
/*  #include <stdlib.h> */
#include <assert.h> 

#include "commondefs.h"
#include "dlllists.h"
#include "debug.h"

/** Malke a list from an element.
    NB: This makes a copy of element!!!
*/

List
list_make(El a)
{
  List ptr;

  ptr = NEW(struct lnode);
  assert(ptr != NULL);
  
  ptr->el = a;
  ptr->prev = NULL;						
  ptr->next = NULL;
  
  return ptr;
}

/* Insertion of an elemnt into a list before where */
/* If where is NULL, insert at end */
List
list_insert(El a, List where,List s)
{
  struct lnode * new=list_make(a);
  
  if(where == NULL)
    return list_append_element(a,s);

  assert(list_is_node(where,s));

  new->prev=where->prev;
  new->next=where;
  where->prev=new;
  if(new->prev) 
    (new->prev)->next=new;

  if(s->prev)
    return s->prev;
  
  return s;
}							

List							
list_concatenate(List la, List lb)				
{							
  List ptr; 						
  	
  /*  
      The second list should be either empty
      or the beginning of a list 
  */
  assert(lb == NULL || lb->prev == NULL);					
  if(la == NULL) 					
    return lb;	
					
  if(lb == NULL)
    return la;

  /*  It holds: la != NULL && lb !=NULL */
  							
  /* go to the last nonempty lnode of la */		
  for(ptr = la; (ptr->next) != NULL; ptr= ptr->next)	
    ;							
		
  
  /* link the two lists */ 				
  ptr->next = lb;
  lb->prev = ptr;
 							
  /* return the beginning of the list */ 		
  return la;						
}

/* Addition of elements */

List							
list_append_element(El a, List s)				
{							
 	
  List ptr1,ptr2;
  
  ptr1 = list_make(a);
  ptr2 = list_concatenate(s,ptr1);

  return ptr2;
}							

List							
list_prepend_element(El a, List s)				
{							
 	
  List ptr1,ptr2;
  
  ptr1 = list_make(a);
  ptr2 = list_concatenate(ptr1,s);

  return ptr2;
}							

					
List							
list_add_element(El a, List s)				
{							
  return list_prepend_element(a,s);
}							

/*    
      Delete the lnode which from l 
      Returns  NULL if 
      l is empty, or
      p was the last lnode, or
      p was not found in l
      
      otherwise returns p->next  
*/
List
list_delete_element(struct lnode *which, List l)
{
  List prev,next;

  /*  
      We call this function provided 
      which is a node of l 
      (this implies that l is nonempty)
  */
  assert(list_is_node(which,l));

  prev = which->prev;
  next = which->next;
  
  if(prev)
    prev->next = next;
  if(next)
    next->prev = prev;
  
  free(which);

  if(prev)
    return l;
  else
    return next;
}

int
list_belongs(El a, List l, int (*eq)(El *,El *))
{		
  struct lnode  *ptr;
  
  FORALLIN(ptr,l)
    { 
      if(eq(&a,&ptr->el)) return 1; 
    }

  return 0;
}							

struct lnode *
list_find(El a, List l, int (*eq)(El *,El *))
{		
  struct lnode  *ptr;
  
  FORALLIN(ptr,l)
    { 
      if(eq(&a,&ptr->el)) return ptr; 
    }

  return NULL;
}							

List
list_filter(List l, int (* boolfun)(El) )
{
  List c,n;
  List beginning = l;

  c = l;

  while(c != NULL)
    {
      n=c->next;

      if(! boolfun(c->el))
	beginning = list_delete_element(c,beginning);

      c=n;
    }

  return beginning;
}

int
list_is_node(struct lnode * ptr, List list)
{
  List p;
  
  FORALLIN(p,list)
    {
      if(p == ptr)
	return 1;
    }

  return 0;
}

List
list_beginning_of(List list)
{
  
  List p;
  
  /*  we call it if list is not empty */ 
  assert(list != NULL);
  
  FORALLINBACK(p,list)
    if (p->prev == NULL) 
      return p;
  
  return p;
}

List 							
list_copy(const List list)
{					
  	
  /*  The list `list` is only to be read */
  List copy,prev,p;					
   
  copy = prev = NULL;

  
  FORALLIN(p,list)
    {
      copy = list_make(p->el);
      
      copy->prev = prev;
      copy->next = NULL;
      /*  Don't try to write in the empty pointer */
      if(prev)
	prev->next = copy;

      prev = copy;
    }

  if(copy == NULL)
    return copy;

  return list_beginning_of(copy);
 							
}							

List 							
list_copy_reverted(const List list)
{					
  	
  /*  The list `list` is only to be read */
  List copy,p;					
   
  copy =  NULL;
  
  FORALLIN(p,list)
    copy = list_prepend_element(p->el,copy);

  if(copy == NULL)
    return copy;

  return list_beginning_of(copy);
 							
}							

int 							
list_free(List s){					
  							
  if(s != NULL){					
    list_free(s->next);					
    free(s);						
  }							
							
  return 1;						
}

int 
list_length(List l)
{
  int i;
  
  for(i = 0; l!= NULL; l=l->next,i++)
    ;
  return i;
}

#endif /*  LISTS_C */

